#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;

// 插入排序(从小到大)
// 1.默认起始元素是有序的
// 2.从第二个元素开始，和前面的元素进行比较，此时不要直接通过和前面的元素比较后就直接交互，而是找到第一个不小于其的元素，在后面插入
//   如果每次没找到，就把前面的元素依次往后移动，用临时变量记录当前元素值



// 时间和空间复杂度
// 时间复杂度：O(n^2)
// 平均时间复杂度：O(n^2)
// 空间复杂度：O(1)
// 最优时间复杂度：O(n) 
// 稳定
// 所有基础算法中最优，对于有序或近似有序的数组，插入排序的时间复杂度为O(n)
// 不用进行交换

void InsertSort(int arr[], int len)
{
    // 默认第一个元素是有序的
    for (size_t i = 1; i < len; i++)
    {
        int val = arr[i];
        size_t j = i;
        // 将比val大的元素向后移动
        while (j > 0 && arr[j-1] > val)
        {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = val;
    }
}

// int main(int argc, const char** argv) {
//     int arr[10];
//     srand(time(NULL));
//     for (int i = 0; i < 10; i++) {
//         arr[i] = rand() % 100;
//         cout << arr[i] << " ";
//     }
//     cout << endl;

//     InsertSort(arr, 10);
//     for (int val : arr)
//         cout << val << " ";
//     cout << endl;
//     return 0;
// }